package leetcode.code1914;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	int m, n;

	public int[][] rotateGrid(int[][] grid, int k) {
		m = grid.length;
		n = grid[0].length;
		int laySize = Math.min(m, n) >> 1;
		int[][] ans = new int[m][n];
		for (int lay = 0, x = 0, y = 0; lay < laySize; lay++, x++, y++) {
			int girth = girth(lay); // 第lay层周长
			int layk = k % girth;// 在这个lay实际上走了几步
			int[] start = new int[] { x, y }; // 第lay层第一个数
			int[] ansStart = null;
			int[] nums = new int[girth]; // lay层所有数
			for (int i = 0; i < girth; i++) { // 取lay层所有数
				if (i == layk) {
					ansStart = new int[] { start[0], start[1] };
				}
				nums[i] = grid[start[0]][start[1]];
				start = move(start[0], start[1], lay);
			}
			// 从ansStart开始向ans数组添加答案
			for (int i = 0; i < girth; i++) { // 取lay层所有数
				ans[ansStart[0]][ansStart[1]] = nums[i];
				ansStart = move(ansStart[0], ansStart[1], lay);
			}
		}
		return ans;
	}

	// 返回lay层，从x，y移动一步后的位置
	private int[] move(int x, int y, int lay) {
		boolean u = x == lay;
		boolean d = m - 1 - x == lay;
		boolean l = y == lay;
		boolean r = n - 1 - y == lay;
		if (l && !d) {// 左边向下
			return new int[] { x + 1, y };
		} else if (d && !r) {// 下边向右
			return new int[] { x, y + 1 };
		} else if (r && !u) {// 右边向上
			return new int[] { x - 1, y };
		} else {// 上边向左 if (u && !l)
			return new int[] { x, y - 1 };
		}
	}

	// layer层周长
	private int girth(int layer) {
		return ((m - layer * 2 + n - layer * 2) << 1) - 4;
	}

	@Override
	public void debug4() {

		H.compare(H.str2array1(
				"[[4035,3336,1046,989,3205,3972,1317,1142,1326,943,955,1781,4538,3425,2235,3443,2608,2951,57,1343,2736,2190,43,3543],[1956,911,3827,333,2026,4002,115,4389,3548,1566,3985,1383,4475,3509,4178,126,536,691,2701,4511,376,4367,2526,1196],[433,34,3967,1257,403,4534,8,3261,2113,775,508,1063,4776,3011,1811,3851,3343,623,282,1787,2146,3899,3610,875],[4345,165,1190,3291,658,1210,3527,738,4229,4023,4145,3985,430,790,1728,645,668,3255,4802,327,316,1494,2248,4722],[447,3092,124,563,3246,4331,3907,4112,2215,1907,37,4115,1948,4046,1931,3838,66,915,1977,3346,4617,1414,2893,4841],[3372,1749,2387,4801,4088,1349,3177,3239,4080,4562,4919,619,470,421,4012,3228,957,3938,2634,3439,1551,4995,4475,4224],[232,3360,596,3961,4571,1397,4930,3686,2633,790,3756,1898,2264,4792,3918,3206,2649,3305,1873,2024,3811,374,2764,475],[3784,2417,402,3764,2183,2649,2298,3169,1094,2621,750,4183,2306,3104,1810,1198,3107,1447,3260,4515,3633,1903,3388,42],[1203,3725,4659,3865,3331,4388,1106,1731,4468,2239,4535,1237,1250,4069,4647,1123,306,4503,3540,4191,876,3791,2228,4349],[1586,1534,2368,2520,1852,2361,4116,3670,1519,2703,4280,1451,2328,2162,2894,3747,2207,1660,2975,3344,2715,4589,968,4166],[4557,3807,1103,779,529,4115,1538,571,2548,1373,2356,2642,993,3758,1313,3156,2488,3789,4430,871,3943,2349,1428,814],[1237,3175,2462,425,2050,2367,3337,2811,4008,2151,4207,1947,3678,3126,3139,4475,309,762,3121,2659,2997,3206,3599,3318],[2759,4404,309,296,3293,3119,866,1944,2830,2195,4700,926,2465,3674,1751,349,2910,787,2797,2483,742,3138,118,4764],[2402,2753,1630,1468,2529,4841,2151,736,1269,4376,2722,320,850,1447,591,3157,447,2454,582,4391,150,4213,1022,2731]]"),
				this.rotateGrid(H.str2array1(
						"[[2190,43,3543,1196,875,4722,4841,4224,475,42,4349,4166,814,3318,4764,2731,1022,4213,150,4391,582,2454,447,3157],[2736,4404,3175,3807,1534,3725,2417,3360,1749,3092,165,34,911,3827,333,2026,4002,115,4389,3548,1566,3985,1383,591],[1343,309,2997,2659,3121,762,309,4475,3139,3126,3678,1947,4207,2151,4008,2811,3337,2367,2050,425,2462,1103,4475,1447],[57,296,3206,3633,876,2715,3943,871,4430,3789,2488,3156,1313,3758,993,2642,2356,1373,2548,571,1538,2368,3509,850],[2951,3293,2349,3811,4280,2703,1519,3670,4116,2361,1852,3331,2183,4571,4088,3246,4331,3907,4112,2215,4115,4659,4178,320],[2608,3119,4589,1551,1451,4069,1250,1237,4535,2239,4468,1731,1106,4388,2649,1397,1349,3177,3239,1907,529,402,126,2722],[3443,866,3791,4617,2328,4647,1094,3169,2298,4930,3686,2633,790,3756,1898,2264,4792,3918,4080,37,779,596,536,4376],[2235,1944,1903,316,2162,1123,2621,750,4183,2306,3104,1810,1198,3107,1447,3305,2649,3206,4562,4115,2520,2387,691,1269],[3425,2830,374,327,2894,306,4503,3540,3260,1873,2634,3938,957,3228,4012,421,470,619,4919,1948,3865,124,2701,736],[4538,2195,4995,4802,3747,2207,1660,2975,3344,4191,4515,2024,3439,3346,1977,915,66,3838,1931,4046,3764,1190,4511,2151],[1781,4700,1414,3255,668,645,1728,790,430,3985,4145,4023,4229,738,3527,1210,658,3291,563,4801,3961,3967,376,4841],[955,926,1494,3899,2146,1787,282,623,3343,3851,1811,3011,4776,1063,508,775,2113,3261,8,4534,403,1257,4367,2529],[943,2465,3674,1751,349,2910,787,2797,2483,742,3138,118,3599,1428,968,2228,3388,2764,4475,2893,2248,3610,2526,1468],[1326,1142,1317,3972,3205,989,1046,3336,4035,1956,433,4345,447,3372,232,3784,1203,1586,4557,1237,2759,2402,2753,1630]]"),
						717433611));
		H.compare(H.str2array1("[[3,4,8,12],[2,11,10,16],[1,7,6,15],[5,9,13,14]]"),
				this.rotateGrid(H.str2array1("[[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]"), 2));
		H.compare(H.str2array1(
				"[[188,2035,4471,2822,3970,1906,3608,298,3072,3546,1502,773],[996,1058,3645,681,2910,2513,4357,4645,3060,743,3076,4388],[3274,1709,4376,3944,2527,3838,63,3829,233,4525,3712,3115],[744,1780,1276,4478,3226,2742,3454,4127,3208,2506,3110,747],[4431,4179,3271,2690,83,4161,2938,1761,4717,3217,2715,3937],[898,304,2587,4153,3297,946,3546,3204,4347,3351,3139,1038],[1086,2443,3725,1273,2968,4214,4549,1897,3452,2278,2227,3838],[2055,2350,161,2292,3268,2610,3766,2862,1601,302,4470,2270],[3797,2278,4095,234,4717,608,1189,4381,3704,703,2778,3832],[1215,4499,1672,3268,1122,4272,4510,509,2344,757,1293,108],[84,2042,1997,2284,4203,1922,2216,701,219,2159,1345,4143],[282,234,4780,2766,550,218,3653,81,66,2157,1835,4896],[2721,1011,4087,1090,4406,3276,1755,1727,1131,4108,3633,2842],[2360,2321,1435,2617,1202,2876,3420,3034,2805,3170,3651,1516]]"),
				this.rotateGrid(H.str2array1(
						"[[3970,1906,3608,298,3072,3546,1502,773,4388,3115,747,3937],[2822,304,4179,1780,1709,1058,3645,681,2910,2513,4357,1038],[4471,2443,218,550,2766,4780,1997,1672,4095,161,4645,3838],[2035,2350,3653,4127,3208,4717,4347,3452,1601,3725,3060,2270],[188,2278,81,3454,3204,1897,2862,4381,3704,2587,743,3832],[996,4499,66,2742,1761,1189,608,509,2344,3271,3076,108],[3274,2042,2157,3226,2938,3766,2610,4510,219,1276,3712,4143],[744,234,2159,4478,4161,4549,4214,4272,701,4376,3110,4896],[4431,1011,757,2690,83,3546,946,1122,2216,3944,2715,2842],[898,4087,703,4153,3297,2968,3268,4717,1922,2527,3139,1516],[1086,1090,302,1273,2292,234,3268,2284,4203,3838,2227,3651],[2055,4406,2278,3351,3217,2506,4525,233,3829,63,4470,3170],[3797,3276,1755,1727,1131,4108,3633,1835,1345,1293,2778,2805],[1215,84,282,2721,2360,2321,1435,2617,1202,2876,3420,3034]]"),
						405548684));
		H.compare(H.str2array1("[[10,20],[40,30]]"), this.rotateGrid(H.str2array1("[[40,10],[30,20]]"), 1));
		H.compare(H.str2array1("[[3,4,8,12],[2,11,10,16],[1,7,6,15],[5,9,13,14]]"),
				this.rotateGrid(H.str2array1("[[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]"), 2));
		this.rotateGrid(H.str2array1("[[40,10],[30,20]]"), 1);
//		[[36,1,2,3,4,5],[6,7,8,9,10,11],[12,13,14,15,16,17],[18,19,20,21,22,23],[24,25,26,27,28,29],[30,31,32,33,34,35]]
//				100
	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
